% Define document
\documentclass[11pt]{scrartcl}

% Import packages
\usepackage[dutch,english]{babel}
\usepackage{graphicx}
\usepackage{caption}
\usepackage{listings}
\usepackage{parskip} % split paragraphs by vertical space
\usepackage{amsfonts}
\usepackage{mathtools}
\usepackage{gensymb}
\usepackage{tabularx} % for multicolumns
\usepackage{polynom} % long devision

\usepackage{tikz} 
\usetikzlibrary{calc,intersections,through,backgrounds}


% Begin document
\begin{document}
\selectlanguage{dutch}


%Add title
\title{Oefeningen TAI: \\
Oefenzitting 4: Uitbreidingsvelden en eindige velden}
\date{}
\maketitle



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% About
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{About}
Uitwerking van oefenziting 4 van Toepassingen van Algebra in Informatica gedoceerd in de 3e Bachelor Informatica aan de KULeuven in 2012.

Latex code van dit document te vinden op:\\
SVN checkout: \texttt{https://oefenzittingen-tai.googlecode.com/svn/trunk/}\\
Google code: \texttt{https://code.google.com/p/oefenzittingen-tai/}

Credits: Peter Roelants, Kim Hens
%TODO: put your name here

Te gebruiken op eigen risico!




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Oef 1 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Opgave 1}

Splits in irreduceerbare factoren over $\mathbb{Z}_{3}$:

(a) $x^5 + 2x^4 + x^3 + x^2 + 2$

(b) $x^7 + x^6 + x^5 - x^3 + x^2 - x - 1$



\subsection*{1: extra info}
(Irreduceerbare polynomen $\mathbb{Z}_{3}$:\\
Graad 1: $x, (x + 1), (x + 2)$\\
Graad 2: $(x^2 + 1), (x^2 + x + 2), (x^2 + 2x + 2)$\\
Graad 3: $(x^3 + 2x^2 + 1), 
(x^3 + x^2 + 2x + 1), 
(x^3 + 2x^2 + x + 1), 
(x^3 + 2x + 1), 
(x^3 + 2x^2 + 2x + 2), 
(x^3 + x^2 + 2), 
(x^3 + x^2 + x + 2), 
(x^3 + 2x + 2)$ )



\subsection*{oplossing 1.(a)}

Nulpunt: -1, horner om nulpunt af te splitsen:\\
\begin{table}[h!]
\centering
\begin{tabular}{ c | c c c c c | c }
	 &		$x^5$ &	$x^4$ &	$x^3$ &	$x^2$ &	$x^1$ &	$x^0$\\
	 &		1 &		2 &		1 &		1 &		0 &		2\\
 	-1 &	 &		-1 &	-1 &	0 & 	-1 &	1\\
 	\hline
 	 &		1 &		1 & 	0 &		1 & 	-1 &	0
\end{tabular}
\end{table}
$\Rightarrow (x^5 + 2x^4 + x^3 + x^2 + 2) = (x + 1)(x^4 + x^3 + x -1)$\\
Verder delen door irreduceerbare veelterm $(x^2 + 1)$ die ook kan afgesplitst worden:\\
\begin{center}
\polylongdiv{x^4 + x^3 + x -1}{x^2 + 1}
\end{center}
$\Rightarrow (x^4 + x^3 + x -1) = (x^2 + 1)(x^2 + x + 2)$\\
$\Rightarrow (x^5 + 2x^4 + x^3 + x^2 + 2) = (x^2 + 1)(x^2 + x + 2)(x + 1)$





\subsection*{oplossing 1.(b)}

Delen door irreduceerbare veelterm $(x^2 + 1)$ die kan afgesplitst worden:\\
\begin{center}
\polylongdiv{x^7 + x^6 + x^5 - x^3 + x^2 - x - 1}{x^2 + 1}
\end{center}
$\Rightarrow (x^7 + x^6 + x^5 - x^3 + x^2 - x - 1) = (x^2 + 1)(x^5 + x^4 - x^2 - x + 2)$ (-3 mod 3 = 0)\\
Verder delen door irreduceerbare veelterm $(x^2 + 2x + 2)$ die ook kan afgesplitst worden:\\
\begin{center}
\polylongdiv{x^5 + x^4 - x^2 - x + 2}{x^2 + 2x + 2}
\end{center}
$\Rightarrow (x^5 + x^4 - x^2 - x + 2) = (x^2 + 2x + 2)(x^3 + 2x^2 + 1)$ (-3 mod 3 = 0)\\
$\Rightarrow (x^7 + x^6 + x^5 - x^3 + x^2 - x - 1) = (x^2 + 1)(x^2 + 2x + 2)(x^3 + 2x^2 + 1)$






%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Oef 2
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Opgave 2}

Toon aan dat $\mathbb{Q}(\frac{-1+\sqrt{3}i}{2})$ het splitsingsveld is van $x^4 + x^2 + 1$ over $\mathbb{Q}$.




\subsection*{oplossing 2.}

Te Bewijzen:

(1) $x^4 + x^2 + 1$ kan ontbonden worden in lineaire factoren in $\mathbb{Q}(\frac{-1+\sqrt{3}i}{2})$

(2) $\mathbb{Q}(\frac{-1+\sqrt{3}i}{2})$ is het kleinste veld waarover $x^4 + x^2 + 1$ kan ontbonden worden in lineaire factoren

\vspace{0.5cm}
(1)\\
$x^4 + x^2 + 1 = 0$\\
stel $x^2 = y \Rightarrow y^2 + y + 1 = 0$\\
$\Rightarrow y_{1,2} = \frac{-1 \pm i \sqrt{3}}{2} = \frac{-1}{2} \pm \frac{\sqrt{3}}{2}i$

Deze nulpunten kunnen we plotten op de eenheidscirkel en omzetten naar een hoek, en dan via de formule van euler ($e^{ix} = cos(x) + i * sin(x)$) omzetten naar:\\
$y_1 = cos(\frac{2\pi}{3}) + i * sin(\frac{2\pi}{3}) = e^{\frac{2\pi}{3}i}$\\
$y_2 = cos(\frac{4\pi}{3}) + i * sin(\frac{4\pi}{3}) = e^{\frac{4\pi}{3}i}$

\begin{tabularx}{\textwidth}{XX}

$x^2 = e^{\frac{2\pi}{3}i} \Rightarrow x = \pm e^{\frac{\pi}{3}i}$

$x_1 = \frac{1}{2} + \frac{\sqrt{3}}{2}i$

$x_2 = - \frac{1}{2} - \frac{\sqrt{3}}{2}i$

&

$x^2 = e^{\frac{4\pi}{3}i} \Rightarrow x = \pm e^{\frac{2\pi}{3}i}$
 
$x_3 = - \frac{1}{2} + \frac{\sqrt{3}}{2}i$

$x_4 = \frac{1}{2} - \frac{\sqrt{3}}{2}i$

\end{tabularx}





\vspace{0.5cm}
(2)\\
\[\mathbb{Q}(\frac{-1+\sqrt{3}i}{2}) = \{ a + b \frac{-1 + \sqrt{3}i}{2} | a, b \in \mathbb{Q} \} \]
\[ = \{ a + b\frac{-1}{2} + \frac{b}{2} \sqrt{3}i  | a, b \in \mathbb{Q} \} \]
\[ = \{ a' + b' \sqrt{3}i  | a', b' \in \mathbb{Q} \} \]




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Oef 3
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Opgave 3}
Zij GF(4) = $\{ 0, 1, \xi, \xi + 1 \}$ met $\xi^2 + \xi + 1 = 0$.

(a) Bepaal alle monische irreduceerbare veeltermen van graad twee over GF(4).

(b) Construeer GF($4^2$) uit GF(4) m.b.v. de veelterm $x^2 + x \xi + \xi$.

(c) Bereken $\alpha^i$ voor $i=0,1,\ldots,15$ met $\alpha^2 + \alpha \xi + \xi = 0$.

(d) Bepaal de minimaalveeltermen van de elementen van GF($4^2$) over GF(4).

(e) Bepaal de primitieve veeltermen van graad 2 over GF(4).



\subsection*{3: extra info}
Irreduceerbare veelterm: p.12 tweede deel cursus.\\
Galoisveld: p.21 tweede deel cursus.\\
Minimaalveelterm: p.23 tweede deel cursus.\\
Cyclotomische nevenklassen: p.25 tweede deel cursus.\\
Primitieve veelterm: p.24 tweede deel cursus.\\




\subsection*{oplossing 3.(a)}

Alle mogelijke monische veeltermen van graad 2 over GF(4) = $\{ 0, 1, \xi, \xi + 1 \}$: ([ir] = irreduceerbaar)\\
\begin{tabularx}{\textwidth}{XX}
$x^2$

\fbox{$x^2 + x + \xi + 1$} [ir]

\fbox{$x^2 + \xi x + \xi$} [ir]

\fbox{$x^2 + (\xi + 1)x + 1$} [ir]

$x^2 + \xi$

$x^2 + x + 1$

$x^2 + \xi x + \xi$

$x^2 + (\xi + 1)x$


&
$x^2 + 1$

\fbox{$x^2 + x + \xi$} [ir]

$x^2 + \xi x$

$x^2 + (\xi + 1)x + \xi + 1$

$x^2 + \xi + 1$

$x^2 + x$

\fbox{$x^2 + \xi x + 1$} [ir]

\fbox{$x^2 + (\xi + 1)x + \xi$} [ir]
\end{tabularx}

GF(4) = GF($2^2$) $\rightarrow$ is in $\mathbb{Z}_{2}$.

Vb checken op reduceerbaarheid veeltermen:
\begin{itemize}
  \item  $x^2 + \xi$\\
  0: $0^2 + \xi = \xi$\\
  1: $1^2 + \xi = 1 + \xi$\\
  $\xi$: $\xi^2 + \xi = 1$ ($\xi^2 + \xi + 1 = 0 \Rightarrow \xi^2 + \xi = -1 = 1$ )\\
  $\xi + 1$: $(\xi + 1)^2 + \xi = (\xi^2 + 2\xi + 1) + \xi = \xi^2 + \xi + 1 = 0$\\
  $\Rightarrow$ $x^2 + \xi$ heeft nulpunt $(\xi + 1)$ $\Rightarrow$  $x^2 + \xi$ is reduceerbaar.
  
  \item $x^2 + x + \xi$\\
  0: $0^2 + 0 + \xi = \xi$\\
  1: $1^2 + 1 + \xi = \xi$ (1+1 = 0 in $\mathbb{Z}_{2}$)\\
  $\xi$: $\xi^2 + \xi + \xi = 1 + \xi$\\
  $\xi + 1$: $(\xi + 1)^2 + (\xi + 1) + \xi = (\xi^2 + 1)+(\xi +1)+\xi = \xi^2 + 2\xi + 2 = \xi^2$\\
  $\Rightarrow$ $x^2 + x + \xi$ is niet reduceerbaar.
\end{itemize}






\subsection*{oplossing 3.(b)}
$GF(4)[x]|_{x^2 + \xi x + \xi}$\\
$x^2 + \xi x + \xi \overset{\alpha}{\Rightarrow} \alpha^2 + \xi \alpha + \xi = 0$ ($\alpha$ is het nulpunt van $x^2 + \xi x + \xi$)

$GF(4^2) = \{ 
0, 1, \xi, \xi + 1, \alpha, \alpha + 1, \alpha + \xi, \alpha + \xi + 1, \alpha \xi, \alpha \xi + 1, \alpha \xi + \alpha, \alpha \xi + \alpha + 1, \alpha \xi + \xi, \alpha \xi + \xi + 1, \alpha \xi + \alpha + \xi, \alpha \xi + \alpha + \xi + 1
 \}$
 
 
 


\subsection*{oplossing 3.(c)}
$\alpha^0 = 1$\\
$\alpha^1 = \alpha$\\
$\alpha^2 = \alpha \xi + \xi$ \hspace{1cm} ($\alpha^2 + \alpha \xi + \xi = 0$)\\
$\alpha^3 = \alpha (\alpha \xi + \xi) = \alpha + \xi + 1$\\
$\alpha^4 = \alpha + \xi$\\
$\alpha^5 = \xi$\\
$\alpha^6 = \alpha \xi$\\
$\alpha^7 = \alpha \xi + \alpha + \xi + 1$\\
$\alpha^8 = \alpha \xi + 1$\\
$\alpha^9 = \alpha \xi + \xi + 1$\\
$\alpha^{10} = \xi + 1$\\
$\alpha^{11} = \alpha \xi + \alpha$\\
$\alpha^{12} = \alpha + 1$\\
$\alpha^{13} = \alpha \xi + \alpha + \xi$\\
$\alpha^{14} = \alpha \xi + \alpha + 1$\\
$\alpha^{15} = 1$\\

(Zie ook vb.19 p.24 tweede deel cursus)





\subsection*{oplossing 3.(d)}
Voor minimaalveeltermen te bepalen eerst cyclotomische nevenklassen bepalen (zie ook vb. 22 p.25 tweede deel cursus).\\
$GF(4^2) \Rightarrow q=4, k=2 \Rightarrow q^k = 16 \Rightarrow \pmod{16 - 1} \Rightarrow \pmod{15}$\\
$\Rightarrow C_{x} = \{ x, x*q \pmod{q^k -1} \} \Rightarrow C_{x} = \{ x, x*4 \pmod{15} \}$\\

$C_{0} = \{ 0, 0*4 \pmod{15} \} = \{ 0 \}$\\
$C_{1} = \{ 1, 1*4 \pmod{15} \} = \{ 1, 4 \}$\\
$C_{2} = \{ 2, 2*4 \pmod{15} \} = \{ 2, 8 \}$\\
$C_{3} = \{ 3, 3*4 \pmod{15} \} = \{ 3, 12 \}$\\
$C_{4} = C_{1}$\\
$C_{5} = \{ 5, 5*4 \pmod{15} \} = \{ 5 \}$\\
$C_{6} = \{ 6, 6*4 \pmod{15} \} = \{ 6, 9 \}$\\
$C_{7} = \{ 7, 7*4 \pmod{15} \} = \{ 7, 13 \}$\\
$C_{8} = C_{2}$\\
$C_{9} = C_{6}$\\
$C_{10} = \{ 10, 10*4 \pmod{15} \} = \{ 10\}$\\
$C_{11} = \{ 11, 11*4 \pmod{15} \} = \{ 11, 14 \}$\\
$C_{12} = C_{3}$\\
$C_{13} = C_{7}$\\
$C_{14} = C_{11}$

Minimaalveeltermen:\\
$C_{0} = \{ 0 \} \rightarrow m^{(0)}  = (x - \alpha^0) = x + 1$\\
$C_{1} = \{ 1, 4 \} \rightarrow m^{(1)} = (x - \alpha^1)(x - \alpha^4) = x^2 + \xi x + \xi$\\
$C_{2} = \{ 2, 8 \} \rightarrow m^{(2)} = (x - \alpha^2)(x - \alpha^8) = x^2 + \xi x + x + \xi + 1$\\
$C_{3} = \{ 3, 12 \} \rightarrow m^{(3)} = (x - \alpha^3)(x - \alpha^{12}) = x^2 + \xi x + 1$\\
$C_{5} = \{ 5 \} \rightarrow m^{(5)} = (x - \alpha^5) = x + \xi$\\
$C_{6} = \{ 6, 9 \} \rightarrow m^{(6)} = (x - \alpha^6)(x - \alpha^{9}) = x^2 + \xi x + x + 1$\\
$C_{7} = \{ 7, 13 \} \rightarrow m^{(7)} = (x - \alpha^7)(x - \alpha^{13}) = x^2 + x + \xi$\\
$C_{10} = \{ 10\} \rightarrow m^{(10)} = (x - \alpha^{10}) = x + \xi + 1$\\
$C_{11} = \{ 11, 14 \} \rightarrow m^{(11)} = (x - \alpha^{11})(x - \alpha^{14}) = x^2 + x + \xi + 1$\\
(minimaalveeltermen mogen geen $\alpha$ meer bevatten omdat het veeltermen over GF(4) zijn en niet over GF($4^2$)!)\\
(Merk op: $x^{15} - 1 = (x + 1)(x^2 + \xi x + \xi)(x^2 + \xi x + x + \xi + 1)(x^2 + \xi x + 1)(x + \xi)(x^2 + \xi x + x + 1)(x^2 + x + \xi)(x + \xi + 1)(x^2 + x + \xi + 1)$)





\subsection*{oplossing 3.(e)}
Primitieve veelterm is een minimaalveelterm van een primitief element (p.24 cursus).\\
Een primitief element is een element dat de multiplicatieve groep van een veld genereert. (p.20 cursus)

%TODO: hoe bepalen?

Primitieve veeltermen graad 2:\\
$x^2 + \xi x + \xi$\\
$x^2 + \xi x + x + \xi + 1$\\
$x^2 + x + \xi$\\
$x^2 + x + \xi + 1$





%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Oef 4
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Opgave 4}
Zij GF(9) = $\{ 0, 1, 2, \alpha, \alpha + 1, \alpha + 2, 2\alpha, 2\alpha+2, 2\alpha + 2 \}$, met $\alpha^2 = 1 - \alpha$.

(a) Ga na dat $x^2 + \alpha x +1$ irreduceerbaar is over GF(9).

(b) Construeer GF(81) door GF(9) uit te breiden met een nulpunt $\xi$ van deze veelterm.

(c) Bepaal de (multiplicatieve) orde van $\xi$. Opmerking: orde$(\xi)|\#GF(81)^{*}$.

(d) (**) Bepaal de multiplicatieve orde van $2 \alpha + (1 + \alpha)\xi$.

  
 
\subsection*{oplossing 4.(a)}
Nagaan dat  $x^2 + \alpha x +1$ niet deelbaar is door de elementen van GF(9).




\subsection*{oplossing 4.(b)}
GF(81) = $\{ a + b \xi | a,b \in GF(9) \}$ met $\xi^2 + \alpha \xi +1 = 0$.
%TODO: uitleggen




\subsection*{oplossing 4.(c)}
$\xi^{10} = 1$
%TODO: correct, uitleggen?


\end{document}
